package com.leetcode.dynamic_programming;

import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/7/12 10:05
 */
public class FindSum {

    public static final int[] arr = new int[]{3, 34, 4, 12, 5, 2};

    public boolean recSubset(int[] arr, int i, int s) {
        if (s == 0) return true;
        else if (i == 0) return arr[0] == s;
            // 不选这一条分支
        else if (arr[i] > s) return recSubset(arr, i - 1, s);
        else {
            // 两条分支，选这个或者不选这个
            boolean a = recSubset(arr, i - 1, s);
            boolean b = recSubset(arr, i - 1, s - arr[i]);
            return a || b;
        }
    }

    public boolean dpSubset(int[] arr, int s) {
        int n = arr.length;
        boolean[][] sub = new boolean[n][s + 1];
        if (arr[0] == s) return true;

        //初始化操作
        Arrays.stream(sub).forEach(booleans -> booleans[0] = true);
        for (int i = 0; i < s + 1; i++) {
            sub[0][i] = false;
        }

        sub[0][arr[0]] = true;

        for (int i = 1; i < n; i++) {
            for (int j = 1; j < s + 1; j++) {
                if (arr[i] > j)
                    sub[i][j] = sub[i - 1][j];
                else
                    sub[i][j] = sub[i - 1][j - arr[i]] || sub[i - 1][j];
            }
        }
        return sub[n - 1][s];
    }

    public static void main(String[] args) {
        FindSum sum = new FindSum();

        System.out.println(sum.dpSubset(arr, 9));
        System.out.println(sum.dpSubset(arr, 10));
        System.out.println(sum.dpSubset(arr, 11));
        System.out.println(sum.dpSubset(arr, 12));
        System.out.println(sum.dpSubset(arr, 13));
    }

}
